unit HashTable;
{
 Basic hash table. Stores TObjects based on a key.
 Note that contrary to a normal hash table, this implementation specifically
 does not allow the insertion of duplicate keys.
 Uses Double Hashing as probe function with the following functions:
 h(k) = h'(k) + i * h''(k)
 h'(k) = k mod M
 h''(k) = 1 + (k mod (M-1))
 Where:
  k = key
  i = probe #
  M = size of hash table

=====================================================
*                                                   *
*      NEVER CREATE WITH A POWER OF 2 AS SIZE!      *
*        Use the FindClosestPrime parameter         *
*    of the constructor and create with at least    *
*    double the number of elements that will be     *
*        stored in it for optimal results           *
*                                                   *
=====================================================
}

interface

type
  HashElement = record
    Key: Integer;
    Item: TObject;
  end;

  THashTable = class
    private
      _table: array of HashElement;
      _size: Integer;
      _numberOfElements: Integer;

      function PrimaryHash(Key: Integer): Integer;
      function SecondaryHash(Key: Integer): Integer;
    public
      constructor Create(Size: Integer; FindClosestPrime: Boolean = false);
      destructor Destroy;

      function Insert(Key: Integer; Item: TObject): Boolean;
      function Search(Key: Integer): TObject;
      function Delete(Key: Integer): Boolean;

      function GetItem(Index: Integer): TObject;

      property Size: Integer read _size;
  end;

implementation

uses
  Math;

const
  EmptyElement: HashElement = (Key: -1; Item: nil);

constructor THashTable.Create(Size: Integer; FindClosestPrime: Boolean = false);
{
  Creates the hash table with the given size.
  FindClosestPrime makes sure the table is created with a prime number as size,
  size will be the highest prime number lower than the given size.
}
var
  i, n, limit: Integer;
  is_prime: array of Boolean;
  element: HashElement;
begin
  inherited Create;
  if (FindClosestPrime) then begin
    // arbitrary search limit
    limit := Size;
    SetLength(is_prime, Size+1);
    // assume all numbers are prime at first
    for i := 0 to limit do begin
      is_prime[i] := true;
    end;

    for n := 2 to Ceil(sqrt(limit)) do begin
      if (is_prime[n]) then begin
        // eliminate multiples of each prime,
        // starting with its square
        // 2n, 3n, ...,  (n-1)n already eliminated
        // nn, (n+1)n, (n+2)n, ... to be eliminated
        is_prime[n] := false;
        i := n * n;
        while (i <= limit) do begin
          is_prime[i] := false;
          i := i + n;
        end;
      end;
    end;

    for i := limit downto 2 do begin
      if (is_prime[i]) then begin
        Size := i;
        break;
      end;
    end;
  end;
  SetLength(_table, Size);
  _size := Size;
  _numberOfElements := 0;

  element.Key := -1;
  element.Item := nil;
  for i := 0 to _size -1 do begin
    _table[i] := EmptyElement;
  end;
end;

destructor THashTable.Destroy;
begin
  inherited Destroy;
end;

function THashTable.Insert(Key: Integer; Item: TObject): Boolean;
{
  Inserts element Item in the hash table based on Key.
  Returns true when successfully inserted, false if the table is full
}
var
  location: Integer;
  probe: Integer;
  element: HashElement;
begin
  location := PrimaryHash(Key);
  probe := 0;
  element.Key := Key;
  element.Item := Item;
  while ((probe < _size) and (_table[location].Key <> -1)) do begin
    if (_table[location].Key = Key) then begin
      result := false;
      exit;
    end;
    probe := probe + 1;
    location := (PrimaryHash(Key) + probe * SecondaryHash(Key)) mod _size;
  end;
  if (probe < _size) then begin
    _table[location] := element;
  end
  else result := false;
end;

function THashTable.Search(Key: Integer): TObject;
{
  Retrieves a TObject based on the Key.
}
var
  probe: Integer;
  location: Integer;
begin
  probe := 0;
  location := PrimaryHash(Key);
  result := nil;
  while ((probe < _size) and (_table[location].Key <> -1)) do begin
    if (_table[location].Key = Key) then begin
      result := _table[location].Item;
      break;
    end
    else begin
      probe := probe + 1;
      location := (PrimaryHash(Key) + probe * SecondaryHash(Key)) mod _size;
    end;
  end;
end;

function THashTable.Delete(Key: Integer): Boolean;
{
  Deletes the item based on the given key.
  Returns true if the item was deleted or false if the item wasn't stored in the table in the first place
}
var
  probe: Integer;
  location: Integer;
begin
  probe := 0;
  location := PrimaryHash(Key);
  result := false;
  while ((probe < _size) and (_table[location].Key <> -1)) do begin
    if (_table[location].Key = Key) then begin
      _table[location] := EmptyElement;
      result := true;
      break;
    end
    else begin
      probe := probe + 1;
      location := PrimaryHash(Key) + probe * SecondaryHash(Key);
    end;
  end;
end;

function THashTable.GetItem(Index: Integer): TObject;
{
  Returns an item based on the index in the hash table, bypassing the hashing functions
  Used for loading and saving the entire hashtable.
}
begin
  result := _table[Index].Item;
end;

function THashTable.PrimaryHash(Key: Integer): Integer;
begin
  result := Key mod _size;
end;

function THashTable.SecondaryHash(Key: Integer): Integer;
begin
  result := 1 + (Key mod (_size-1));
end;

end.
